/*
 * bloom_filter.cpp
 *
 *  Created on: 2012-8-22
 *      Author: yelu01
 */

#include <cassert>
#include <climits>
#include <ctime>
#include <stdint.h>
#include <float.h>
#include <cmath>
#include <algorithm>
#include "bloom_filter.h"

bloom_filter_t::bloom_filter_t()
{
	_num_keys = 1024;
	_num_bits = 0;
	_num_hashfuncs = 0;
	_pf = 0.01;
	_byte_arr = NULL;
}

bloom_filter_t::~bloom_filter_t()
{
	_num_bits = 0;
	_num_hashfuncs = 0;
	_seeds.clear();
	free(_byte_arr);
	_byte_arr = NULL;
}

int bloom_filter_t::create(uint64_t nkeys, double pf)
{
	// do some clearing job.
	_num_keys = nkeys;
	_pf = pf;
	_num_bits = 0;
	_num_hashfuncs = 0;
	_seeds.clear();
	free(_byte_arr);
	int ret = _calc_optimal_params();
	CHECK_EQ_ZERO(ret, return -1, "failed to calc optimal params.");
	// reserve enough space for vector to avoid exceptions.
	try
	{
		_seeds.reserve(_num_hashfuncs);
	}
	catch(std::exception& e)
	{
		LOG(WARNING, "err when reserve space for vertor: %s", e.what());
		return -1;
	}
	_generate_hash_seeds();

	// alloc memory for byte array for storing bits.
	uint64_t num_bytes = 0;
	if(0 == (_num_bits % 8)) { num_bytes = (_num_bits / 8); }
	else { num_bytes = (_num_bits / 8) + 1; }
	_byte_arr = (char*)calloc(num_bytes, sizeof(char));
	CHECK_NOT_NULL(_byte_arr, return -1, "faile to alloc memory for _byte_arr.");

	LOG(DEBUG, "bloom filter created.[num_hashfuncs:%u][num_bits:%llu(%u M)]",
					_num_hashfuncs, _num_bits, _num_bits/(8*1024*1024));

	return 0;
}

void bloom_filter_t::_calc_bit_idx(uint64_t hash,uint64_t& byte_idx,
									uint32_t& bit_idx)
{
	uint64_t bit = hash % _num_bits;
	byte_idx = bit / 8;
	bit_idx = bit % 8;
	return;
}

int bloom_filter_t::insert(const void* key, uint32_t key_len)
{
	if(0 >= key_len || NULL == key) { return -1; }
	uint64_t byte_idx = 0;
	uint32_t bit_idx = 0;
	for(size_t i = 0; i < _seeds.size(); ++i)
	{
		_calc_bit_idx(murmur_hash_64A(key, key_len, _seeds[i]),
										byte_idx, bit_idx);
		_byte_arr[byte_idx] |= (1 << bit_idx);
	}
	return 0;
}

bool bloom_filter_t::may_contain(const void* key, uint32_t key_len)
{
	uint64_t byte_idx = 0;
	uint32_t bit_idx = 0;
	for(size_t i = 0; i < _seeds.size(); ++i)
	{
		_calc_bit_idx(murmur_hash_64A(key, key_len, _seeds[i]),
										byte_idx, bit_idx);
		if((_byte_arr[byte_idx] & (1 << bit_idx)) != (1 << bit_idx))
		{
			return false;
		}
	}
	return true;
}

int bloom_filter_t::_calc_optimal_params()
{
	// The following will attempt to find the number of hash functions
	// and minimum amount of storage bits required to construct a bloom
	// filter consistent with the user defined false positive probability
	// and estimated element insertion count.
	const uint32_t max_hashfuncs = 128;
	const uint64_t max_bits = 8589934592;	// 1G,1*1024*1024*1024*8
	const uint32_t min_hashfuncs = 1;
	const uint64_t min_bits = 8;
	if(_num_keys <=0 || _pf < 0.0)
	{
		LOG(WARNING, "wrong params.[_num_keys:%llu][_pf:%f]", _num_keys, _pf);
		return -1;
	}

	// k = -ln(p)/ln(2), m = -nln(p)/(ln(2))^2.
	// refer to http://en.wikipedia.org/wiki/Bloom_filter
	double k = 0 - std::log(_pf)/std::log(2);
	double m = 0 - _num_keys * std::log(_pf) * std::log(2.71828183)/
				(std::log(2) * std::log(2));

	LOG(DEBUG, "[optimal hashfuncs:%f][optimal bits:%f]", k, m);

	// use max and min to limit m and k.
	if(k > max_hashfuncs)
	{
		_num_hashfuncs = max_hashfuncs;
		LOG(WARNING, "requited hash functions exceed limits." \
						"[required:%f][max:%u]", k, max_hashfuncs);
	}
	else if(k < min_hashfuncs) {_num_hashfuncs = min_hashfuncs;}
	else {_num_hashfuncs = (uint32_t)k;}

	if(m > max_bits)
	{
		_num_bits = max_bits;
		LOG(WARNING, "requited bits exceed limits." \
						"[required:%f][max:%llu]", m, max_bits);
	}
	else if(m < min_bits) {_num_bits = min_bits;}
	else {_num_bits = (uint64_t)m;}
	_num_bits += (((_num_bits % 8) != 0) ? (8 - (_num_bits % 8)) : 0);

	return 0;
}

void bloom_filter_t::_generate_hash_seeds()
{
	// A distinct hash function need not be implementation-wise distinct. In the
	// current implementation "seeding" a common hash function with different
	// values seems to be adequate.
	const uint32_t predef_seed_count = 128;
	static const uint32_t predef_seeds[predef_seed_count] =
	{
		0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
		0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
		0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
		0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
		0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
		0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
		0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
		0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
		0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
		0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
		0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
		0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
		0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
		0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
		0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
		0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
		0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
		0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
		0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
		0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
		0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
		0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
		0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
		0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
		0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
		0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
		0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
		0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
		0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
		0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
		0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
		0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
	};
	uint32_t random_seed = rand() % UINT32_MAX;
	if (_num_hashfuncs <= predef_seed_count)
	{
		std::copy(predef_seeds, predef_seeds + _num_hashfuncs,
					std::back_inserter(_seeds));
		for (size_t i = 0; i < _seeds.size(); ++i)
		{
			// This is done to integrate the user defined random seed, so as
			// to allow for the generation of unique bloom filter instances.
			_seeds[i] = _seeds[i] * _seeds[(i + 3) % _seeds.size()] + random_seed;
		}
	}
	else
	{
		std::copy(predef_seeds, predef_seeds + predef_seed_count,
					std::back_inserter(_seeds));
		srand(random_seed);
		while (_seeds.size() < _num_hashfuncs)
		{
			uint32_t current_seed = (uint32_t)(rand()) * (uint32_t)(rand());
			// skip zero and existing seed.
			if (0 == current_seed) continue;
			if (_seeds.end() == std::find(_seeds.begin(), _seeds.end(),
											current_seed))
			{
				_seeds.push_back(current_seed);
			}
		}
	}
	for (std::vector<uint32_t>::iterator ite = _seeds.begin(); ite != _seeds.end(); ite++)
	{
		LOG(DEBUG, "seed:%u", *ite);
	}
}

uint64_t bloom_filter_t::serialize(FILE* fp)
{
	uint64_t total_len = 0;
	// write _num_bits
	uint64_t len = fwrite(&_num_bits, sizeof(_num_bits), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to serialize _num_bits.");
	total_len += (sizeof(_num_bits) * len);
	// write _num_keys
	len = fwrite(&_num_keys, sizeof(_num_keys), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to serialize _num_keys.");
	total_len += (sizeof(_num_keys) * len);
	// write _num_hashfuncs
	len = fwrite(&_num_hashfuncs, sizeof(_num_hashfuncs), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to serialize _num_hashfuncs.");
	total_len += (sizeof(_num_hashfuncs) * len);
	// write _pf
	len = fwrite(&_pf, sizeof(_pf), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to serialize _pf.");
	total_len += (sizeof(_pf) * len);
	// write _byte_arr
	uint64_t num_bytes = _num_bits / 8;
	if(0 != (_num_bits % 8)) { num_bytes += 1; }
	len = fwrite(_byte_arr, 1, num_bytes, fp);
	CHECK_TRUE(len > 0, return 0, "failed to serialize _byte_arr.");
	total_len += (1 * len);
	// write _seeds
	for(uint32_t i = 0; i < _num_hashfuncs; i++)
	{
		uint32_t n = _seeds[i];
		len = fwrite(&n, sizeof(uint32_t), 1, fp);
		CHECK_TRUE(len == 1, return 0, "failed to serialize _seeds[%u]", i);
		total_len += (sizeof(uint32_t) * len);
	}
	return total_len;
}

uint64_t bloom_filter_t::deserialize(FILE* fp)
{
	uint64_t total_len = 0;
	// read _num_bits
	uint64_t len = fread(&_num_bits, sizeof(_num_bits), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to deserialize _num_bits.");
	total_len += (sizeof(_num_bits) * len);
	// fread _num_keys
	len = fread(&_num_keys, sizeof(_num_keys), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to deserialize _num_keys.");
	total_len += (sizeof(_num_keys) * len);
	// fread _num_hashfuncs
	len = fread(&_num_hashfuncs, sizeof(_num_hashfuncs), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to deserialize _num_hashfuncs.");
	total_len += (sizeof(_num_hashfuncs) * len);
	// fread _pf
	len = fread(&_pf, sizeof(_pf), 1, fp);
	CHECK_TRUE(len == 1, return 0, "failed to deserialize _pf.");
	total_len += (sizeof(_pf) * len);
	// fread _byte_arr
	uint64_t num_bytes = _num_bits / 8;
	if(0 != (_num_bits % 8)) { num_bytes += 1; }
	if(_byte_arr){ free(_byte_arr); }
	_byte_arr = (char*)calloc(num_bytes, 1);
	CHECK_NOT_NULL(_byte_arr, return 0, "failed to calloc memory for _byte_arr.");
	len = fread(_byte_arr, 1, num_bytes, fp);
	CHECK_TRUE(len > 0, return 0, "failed to deserialize _byte_arr.");
	total_len += (1 * len);
	// fread _seeds
	// reserve enough space for vector to avoid exceptions.
	try
	{
		_seeds.clear();
		_seeds.reserve(_num_hashfuncs);
	}
	catch(std::exception& e)
	{
		LOG(WARNING, "err when reserve space for vertor: %s", e.what());
		return 0;
	}
	uint32_t n = 0;
	for(uint32_t i = 0; i < _num_hashfuncs; i++)
	{
		len = fread(&n, sizeof(uint32_t), 1, fp);
		CHECK_TRUE(len == 1, return 0, "failed to deserialize _seeds[%u]", i);
		_seeds.push_back(n);
		total_len += (sizeof(uint32_t) * len);
	}
	return total_len;
}
